public class Sort {

	public static void main(String[] args) {
		Sort sort = new Sort();

		int[] arr = new int[] { 9, 8, 8, 7, 6, 5, 5, 4, 3, 2, 2, 1 };
		//int[] arr = new int[]{1,4,3,0,0,3};
		sort.quickSort(arr);

		for (int i = 0; i < arr.length; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	public void quickSort(int[] arr) {
		quickSort(arr, 0, arr.length - 1);
	}

	private void quickSort(int[] arr, int h, int t) {
		int i = h, j = t;
		int pivot = arr[(h + t) / 2];

		/**
		 * Use i<j, when i==j, the element will be sorted twice in next pass
		 * use i<=j, i,j will never ends as the same
		 */
		while (i <= j) {
			/**
			 * must use > and <, not >= or <=, in case pivot is the largest or smallest 
			 */
			while (arr[i] < pivot)
				++i;
			while (arr[j] > pivot)
				--j;
			
			/**
			 * if use i<j here,when i==j (both point to a pivot), it goes to dead loop
			 */
			if (i <= j) {
				swap(arr, i, j);
				++i;
				--j;
			}
		}

		if (i < t)
			quickSort(arr, i, t);
		if (h < j)
			quickSort(arr, h, j);
	}

	private void swap(int[] arr, int i, int j) {
		if (i != j) {
			arr[i] ^= arr[j];
			arr[j] ^= arr[i];
			arr[i] ^= arr[j];
		}
	}

}
